COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input basic
C00008 ENDMK
C⊗;
\input basic
\def\xskip{\hskip 7pt plus 3pt minus 4pt}
\noindent \bf Demand paging.

Consider a program on a virtual machine capable of storing $b$ ``pages'' of a
fixed size in its high-speed memory. While the program is running it references a
sequence of pages given by the ``page trace''
$$p↓1\,p↓2\ldotsm p↓n\,.$$
Suppose $S↓j$ is the set of $b$ pages in high-speed memory just after $p↓j$ is
referenced; we need $p↓j\in S↓j$. If $p↓j\notin S↓{j-1}$, a ``page fault'' occurs;
some page $q↓j$ in $S↓{j-1}$ is ``pulled'' and we have $S↓j=
S↓{j-1}-\{q↓j\}+\{p↓j\}$,
exchanging $p↓j$ for $q↓j$. It is convenient to assume that the program starts out
with a set $S↓0$ of $b$ completely null pages, and that $q↓j=p↓j$ when there is
no page fault.

It is of interest to consider the best possible sequence of page pulls (the
sequence that minimizes the total number of page faults) for a given page trace
$p↓1\,p↓2\ldotsm p↓n\,$, even though it may be impossible actually to achieve this
optimum sequence in practice because it may require knowing the future page
requests $p↓{j+1}\ldotsm p↓n$ at the time $q↓j$ must be chosen.

\vskip 3pt
\noindent a)\xskip (15 points)

The purpose of this problem is to give a constructive proof that an optimum
strategy is obtained by the following rule:\xskip ``When $p↓j\notin S↓{j-1}$, let
$q↓j$ be an element of $S↓{j-1}$ that does not appear in $\{p↓{j+1},\ldotss,
p↓n\}$, if possible. Otherwise (i.e., if all elements of $S↓{j-1}$ occur again),
let $q↓j$ be the element whose first occurrence in $p↓{j+1}\ldotsm p↓n$ is
{\sl after} all the other pages of $S↓{j-1}$ have occurred.''

The proof can be obtained by repeatedly applying the following idea:\xskip
``Given a page trace $p↓1\,p↓2\ldotsm p↓n$ and a corresponding sequence of
page pulls $q↓1\,q↓2\ldotsm q↓n$ such that, for some $j$ with $p↓j≠q↓j\,$, there is
an element $q\in S↓{j-1}$ and an index $k>j$ such that $q$ does not appear
in $p↓{j+1}\ldotsm p↓k$ but $q↓j=p↓k$, then there is another sequence of
page pulls $q↑\prime↓1\,q↑\prime↓2\ldotsm q↑\prime↓n$ such that $q↑\prime↓1\ldotsm
q↑\prime↓{j-1}=q↓1\ldotsm q↓{j-1}$ and $q↑\prime↓j=q$ and $q↑\prime↓1\,q↑\prime↓2
\ldotsm q↑\prime↓n$ has no more page faults than $q↓1\,a↓2\ldotsm q↓n$.''

The required sequence $q↑\prime↓1\,q↑\prime↓2\ldotsm q↑\prime↓n$ can be
constructed in the following way: Let $m$ be as large as possible such that $q$
does not appear in $q↓{j+1}\ldotsm q↓m$ or in $p↓{j+1}\ldotsm p↓m$. Let
$r↓j=q↓j$, and for $j<i≤m$  let
$$\baselineskip 15pt\vcenter{
\halign{$\hfill#$⊗$\null#\hfill$⊗\quad$\hfill#$⊗$\null#\hfill$⊗\quad#\hfill\cr
q↑\prime↓i⊗=p↓i,⊗r↓i⊗=q↓i,⊗if $p↓i=r↓{i-1}$;\cr
q↑\prime↓i⊗=q↓i,⊗r↓i⊗=r↓{i-1},⊗otherwise.\cr}}$$
Finally if $m<n$ let $q↑\prime↓{m+1}=r↓m$, and let $q↑\prime↓i=q↓i$ for $m+1<i≤n$.

Prove that $S↑\prime↓i=S↓i-\{q\}+\{r↓i\}$ for $j≤i≤m$ and $S↑\prime↓i=S↓i$ for
all $i>m$. And prove that the sequence of page pulls $q↑\prime↓1\,q↑\prime↓2
\ldotsm q↑\prime↓n$ leads to no more page faults than $q↓1\,q↓2\ldotsm q↓n$ does.

\vskip 9pt
\noindent b)\xskip (5 points)

One of the page pulling algorithms often used in practice is the so-called
``least recently used'' rule:\xskip If $p↓j\notin S↓{j-1}$, the page $q↓j$ that is
pulled is a null page if any null pages are present, otherwise $q↓j$ is the page
whose last occurrence in $p↓1\ldotsm p↓{j-1}$ comes before occurrences of all
the other pages in $S↓{j-1}$.

Construct a page trace scheme for which this rule leads to about $b$ times as
many page faults as the optimum strategy does.